/**
 * @author DCSGO
 * @version 1.0
 * 来自微软
 * leetcode 2384. 最大回文数字
 * https://leetcode.cn/problems/largest-palindromic-number/
 * 给定一个字符串s，只含有0~9这些字符
 * 你可以使用来自s中的数字，目的是拼出一个最大的回文数使用数字的个数，不能超过s里含有的个数
 * 比如:
 * 39878，能拼出的最大回文数是:898
 * 00900，能拼出的最大回文数是:9
 * 54321，能拼出的最大回文数是:5
 * 00000，能拼出的最大回文数是:0
 * 最终的结果以字符串形式返回
 * str的长度为N, 1<=N<=100000
 */

/*
左右两边同时进行 每次取一个可用次数 >= 2 的最大数
由外到内进行生成回文数 当所有数的可用次数都不 >= 2
后 选出可用次数为 1 中最大的数 作为回文数的中间的数字
最大回文数生成完毕
需要注意的是0不能作为回文数的开头和结尾 即第一个选取的最大数不能是0
当给的数都是0时中间数就是0 即选出的数的可用次数 > 1
中间的单个数字可以不存在
 */
public class P6 {
    public static void main(String[] args) {
        String s = "39878";
        //回文数的左半部分
        StringBuilder left = new StringBuilder();
        char[] chars = s.toCharArray();
        int[] count = new int[10];
        //遍历字符串 统计数字个数
        for (char ch : chars) {
            count[ch - '0']++;
        }

        //找出最大回文数的左半部分
        int maxIndex = -1;
        while (true) {
            //找出现次数大于2次的最大数
            for (int i = 9; i >= 0; i--) {
                if (count[i] >= 2) {
                    maxIndex = i;
                    break;
                }
            }
            if (maxIndex != -1) {
                //0不能作为左半部分的开头 走进这个 if 表明回文数只可能是一位数
                if (left.length() == 0 && maxIndex == 0) {
                    break;
                }
                //可以次数 - 2(左右各一个) 并将其追加到左半部分
                count[maxIndex] -= 2;
                left.append(maxIndex);
                maxIndex = -1;
            } else {//没有可用次数 >= 2 的数字了
                break;
            }
        }

        //回文数的右半部分 -> 左半部分逆序
        StringBuilder right = new StringBuilder(left).reverse();

        //中间的数 用最大数
        for (int i = 9; i >= 0; i--) {
            if (count[i] >= 1) {//特殊情况：给的数字都是 0
                left.append(i);
                break;
            }
        }

        String ans = new String(left.append(right));
        System.out.println(ans);
    }
}
